#
# @lc app=leetcode.cn id=222 lang=python3
#
# [222] 完全二叉树的节点个数
#
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
# @lc code=start
# Definition for a binary tree node.

class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if root is None:
            return 0
        left = root.left
        right = root.right
        leftHeight = 0
        rightHeight = 0
        while left:
            left = left.left
            leftHeight += 1
        while right:
            right = right.right
            rightHeight += 1
        if leftHeight == rightHeight:
            return (2 << leftHeight) - 1
        return self.countNodes(root.left) + self.countNodes(root.right) + 1
# @lc code=end

